class Solution(object):
    def swimInWater(self, grid):
        n = len(grid)
        st = [0] * n ** 2
        for i in range(n):
            for j in range(n):
                st[grid[i][j]] = i * n + j
        p = [i for i in range(n ** 2)]

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rx = find(x)
            ry = find(y)
            if rx != ry:
                if rx > ry:
                    p[rx] = ry
                else:
                    p[ry] = rx

        for i in range(n ** 2):
            id = st[i]
            x, y = st[i] // n, st[i] % n
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < n and 0 <= uy < n and grid[ux][uy] < grid[x][y]:
                    union(id, ux * n + uy)
            if find(0) == find(n ** 2 - 1):
                return i




data = Solution()
grid = [[0, 2], [1, 3]]
print(data.swimInWater(grid))
